In this paper we consider shortest path problems in a directed graph wherethe transitions between nodes are subject to uncertainty. We use a minimaxformulation, where the objective is to guarantee that a special destinationstate is reached with a minimum cost path under the worst possible instance ofthe uncertainty. Problems of this type arise, among others, in planning andpursuit-evasion contexts, and in model predictive control. Our analysis makesuse of the recently developed theory of abstract semicontractive dynamicprogramming models. We investigate questions of existence and uniqueness ofsolution of the optimality equation, existence of optimal paths, and thevalidity of various algorithms patterned after the classical methods of valueand policy iteration, as well as a Dijkstra-like algorithm for problems withnonnegative arc lengths.
展开▼
